class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []


    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.stack.append(x)

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.stack.pop()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.stack[-1]


    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        if len(self.stack) == 0:
            return True
        else:
            return False
'''上面的方法可能不太合适，因为题中要求的是用队列实现，注意题中的要求，只能用队列操作'''


import collections
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.que = collections.deque()



    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        n = len(self.que)
        self.que.append(x)
        for _ in range(n):
            self.que.append(self.que.popleft())

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.que.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.que[0]


    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        if len(self.stack) == 0:
            return True
        else:
            return False

